package Leetcode;

import base.TreeNode;

import java.util.Stack;

/**
 * @Author piper
 * @Date 2019/10/28 10:57 上午
 */
public class 力扣101_对称二叉树 {

    /**
     * 递归法
     */
    static boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }

    static boolean isSymmetric(TreeNode l, TreeNode r) {
        if (!check(l, r)) return false;
        if (l == null && r == null) return true;
        return isSymmetric(l.left, r.right) && isSymmetric(l.right, r.left);
    }


    /**
     * 迭代法
     */
    static boolean isSymmetric1(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> sl = new Stack<>();
        Stack<TreeNode> sr = new Stack<>();
        sl.push(root.left);
        sr.push(root.right);

        if (root == null) return true;
        TreeNode l, r;

        while (!sl.empty()) {
            l = sl.pop();
            r = sr.pop();
            if (!check(l, r)) return false;
            if (l != null && r != null) {
                sl.push(l.left);
                sr.push(r.right);
                sr.push(l.right);
                sl.push(r.left);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(2);
        TreeNode d = new TreeNode(3);
        TreeNode e = new TreeNode(4);
        TreeNode f = new TreeNode(4);
        TreeNode g = new TreeNode(3);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        System.out.println(isSymmetric(a));
    }

    static boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return true;
    }

}
